package 代码随想2._2链表;

/**
 * @author XXX
 * @date 2024-01-14 13:32
 */

/**
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
 * 快慢指针
 */
public class _5删除链表的倒数第N个节点 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        //只要快慢指针相差 n 个结点即可
        for (int i = 0; i < n  ; i++){
            fastIndex = fastIndex.next;
        }

        while (fastIndex.next != null){
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        //此时 slowIndex 的位置就是待删除元素的前一个位置。
        //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        slowIndex.next = slowIndex.next.next;
        return dummyNode.next;
    }

    //计算节点总数法
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        if(head==null)
            return null;
        ListNode cur = head;
        int cnt = 0;
        while(cur!=null){
            cnt++;
            cur = cur.next;
        }
        ListNode res = new ListNode(0);
        res.next = head;
        cur = res;
        for(int i=1;i<=cnt-n;i++)
            cur = cur.next;
        if(cur.next!=null)
            cur.next = cur.next.next;
        return res.next;
    }
}
